;;Recursão exponencial:
(define power*
  (lambda (x n)
    (if (= n 1)
        x
        (* x (power* x (- n 1))))))

(power* 2 5)

;;Recursão linear:
(define power-aux
  (lambda (x n acc)
    (if (= n 0)
        acc
        (power-aux x
                   (- n 1)
                   (* x acc)))))

(define power
  (lambda (x n)
    (power-aux x (- n 1 ) x)))

(power-aux 3 4 3)

(define list-insert-aux
  (lambda (elt lst pos)
    (if (= pos 0)
        (cons elt lst)
        (cons (car lst)
              (list-insert-aux elt
                               (cdr lst)
                               (- pos 1))))))

(define list-insert
  (lambda (elt lst pos)
    (if (or (negative? pos)
            (> pos (length lst)))
        (error "list-insert: pos is too far ahead")
        (list-insert-aux elt lst pos))))

(list-insert 'x '(a b c) 0)
(list-insert 'x '(a b c) 2)
(list-insert 'x '(a b c) 3)

(define list-insert-tail-rec-aux
  (lambda (elt lst pos left)
    (if (= pos 0)
        (append (reverse left)
                (cons elt lst))
        (list-insert-tail-rec-aux elt
                                  (cdr lst)
                                  (- pos 1)
                                  (cons (car lst) left)))))

(define list-insert-tail-rec
  (lambda (elt lst pos)
    (if (or (negative? pos)
            (> pos (length lst)))
        (error "list-insert: pos is too far ahead")
        (list-insert-tail-rec-aux elt lst pos (list)))))
                                  
(list-insert-tail-rec 'x '(a b c) 2)

;;aproximação áurea:
(define calcula-phi
  (lambda (valor tolerancia)
    (let ((proximo (+ 1 (/ 1 valor))))
      (let ((erro (abs (- proximo valor))))
        (if (>= erro tolerancia)
            (calcula-phi proximo tolerancia)
            proximo)))))

(calcula-phi 1 0.00001)

;;torres de hanoi
(define move
  (lambda (n from to extra)
    (if (zero? n)
        (display "")
        (begin
          (move (- n 1) from extra to)
          (display from)
          (display " -> ")
          (display to)
          (newline)
          (move (- n 1) extra to from)))))

(move 3 'A 'B 'C)


